/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/unique-binary-search-trees-ii
   @Language: C++
   @Datetime: 19-07-10 10:35
   */

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
	vector<TreeNode*> bst(int begin, int back){
		vector<TreeNode*> vs;
		if(begin>back){
			vs.push_back(NULL);
			return vs;
		}
		for(int i=begin; i<=back; ++i){
			vector<TreeNode*> lefts = bst(begin,i-1);
			vector<TreeNode*> rights = bst(i+1,back);
			for(const auto &l:lefts)
				for(const auto &r:rights){
					TreeNode *node=new TreeNode(i);
					node->left=l;
					node->right=r;
					vs.push_back(node);
				}
		}
		return vs;
	}
public:
	vector<TreeNode*> generateTrees(int n) {
		if(n==0) return {};
		return bst(1,n);
	}
};
